#include <stdio.h>
#include <stdlib.h>

typedef struct node 
{
	int data;
	struct node *next;
} node_t;

node_t *header = NULL;

static int init_node(int num)
{
	int i=0;
	node_t *cur, *next;
	size_t size = 0;

	size = sizeof(node_t);
	header = malloc(size);
	header->data = 1;
	header->next = header;

	if(header)
	{
		cur = header;
		for(i=1;i<num;i++)
		{
			next = malloc(size);
			next->data = i+1;
			next->next = NULL;

			cur->next = next;
			cur = next;

			if(i==num-1)
				cur->next = header;
		}
	}

	return 0;
}

static node_t * remove_node(node_t *node)
{
	node_t *pre, *cur;

	pre = header;
	cur = header->next;

	while(cur && cur != header)
	{
		if(cur == node) {
			pre->next = cur->next;
			break;
		}

		pre = cur;
		cur = cur->next;
	}

	if(node == header)
	{
		header = header->next;
		pre->next = header;
	}

	return cur;
}

static void each_node()
{
	node_t *cur;

	cur = header;
	do {
		printf("%p=%d,", cur, cur->data);
		cur = cur->next;
	}
	while(cur && cur != header);

	printf("\n");
}


#define LIST

#ifdef LIST
int main(int argc, char **argv)
{
	int num=0;
	node_t *cur;

	num = atoi(argv[1]);
	if(num == 0) return -1;

	init_node(num);	
	each_node();

	//remove_node(header);
	
	cur = header;
	while(cur)
	{
		if(cur->next == cur) break;
		cur = remove_node(cur->next);
		if(cur) {
			printf("remove %p=%d\n", cur, cur->data);
			cur = cur->next;
		}
	}

	each_node();

	return 0;
}

#else

int main()
{
	int n, m=3, i, s = 0;
	printf ("N = ");
	scanf("%d", &n);
	for (i = 2; i <= n; i++)
	{
		s = (s + m) % i;
	}
	printf ("\nThe winner is %d\n", s+1);
}

#endif
